翻訳と辞書 Words near each other ・ Rochaeva ・ Rochak Kohli ・ Rochal ・ Rochaliki ・ Rochambeau ・ Rochambeau Farm ・ Rochambeau Library-Providence Community Library ・ Rochambeau Monument (Newport, Rhode Island) ・ Rochan ・ Rochard ・ Rochas ・ Rochas Okorocha ・ Rochat ・ Rochat-Louise-Sauerwein Block ・ Rochau ・ Rocha–Thatte cycle detection algorithm ・ Rochdale ・ Rochdale (ancient parish) ・ Rochdale (car) ・ Rochdale (disambiguation) ・ Rochdale (UK Parliament constituency) ・ Rochdale A.F.C. ・ Rochdale A.F.C. (1896) ・ Rochdale Branch Canal ・ Rochdale by-election ・ Rochdale by-election, 1940 ・ Rochdale by-election, 1958 ・ Rochdale by-election, 1972 ・ Rochdale Canal ・ Rochdale Castle Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Rocha–Thatte cycle detection algorithm ： ウィキペディア英語版 Rocha–Thatte cycle detection algorithm Rocha–Thatte algorithm is a distributed algorithm in graph theory for detecting cycles on large-scale directed graphs based on the bulk synchronous message passing abstraction. This algorithm for detecting cycles by message passing is suitable to be implemented in distributed graph processing systems, and it is also suitable for implementations in systems for disk-based computations, such as the GraphChi, where the computation is mainly based on secondary memory. Disk-based computations are necessary when we have a single computer for processing large-scale graphs, and the computation exceeds the primary memory capacity. == Overview == The Rocha–Thatte algorithm is a general algorithm for detecting cycles in a directed graph $G$ by message passing among its vertices, based on the bulk synchronous message passing abstraction. This is a vertex-centric approach in which the vertices of the graph work together for detecting cycles. The bulk synchronous parallel model consists of a sequence of iterations, in each of which a vertex can receive messages sent by other vertices in the previous iteration, and send messages to other vertices. In each pass, each active vertex of $G$ sends a set of sequences of vertices to its out-neighbours as described next. In the first pass, each vertex $v$ sends the message $(v)$ to all its out-neighbours. In subsequent iterations, each active vertex $v$ appends $v$ to each sequence it received in the previous iteration. It then sends all the updated sequences to its out-neighbours. If $v$ has not received any message in the previous iteration, then $v$ deactivates itself. The algorithm terminates when all the vertices have been deactivated. For a sequence $(v\_1,\; v\_2,\; \backslash ldots\; ,\; v\_k)$ received by vertex $v$, the appended sequence is not forwarded in two cases: (i) if $v\; =\; v\_1$, then $v$ has detected a cycle, which is reported; (ii) if $v\; =\; v\_i$ for some $i\; \backslash in$, then $v$ has detected a sequence that contains the cycle $(v\; =\; v\_i,\; v\_i+1,\; \backslash ldots\; ,\; v\_k,\; v\_k+1\; =\; v)$; in this case, the sequence is discarded, since the cycle must have been detected in an earlier iteration; to be precise, this cycle must have been detected in iteration $k\; -\; i\; +\; 1$. Every cycle $(v\_1,\; v\_2,\; \backslash ldots\; ,\; v\_k,\; v\_k+1\; =\; v\_1)$ is detected by all $v\_i,\; i\; =\; 1$ to $k$ in the same iteration; it is reported by the vertex $\backslash min\backslash$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Rocha–Thatte cycle detection algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.